^This application interface uses Plotter, by Matt Morse,
NeXT Technical Publications Department
Times-Roman
Traveling Salesman Problem
;Nolan R. Davis and Joseph Jeffery
Naval Research Laboratory
Times-BoldItalic
%An Application of Simulated Annealing
Times-Bold
Button1_TOZTHcT
Field4hT
Field5mT
Field6pT
[2934c]{\rtf0\ansi{\fonttbl\f0\fswiss Helvetica;}
\margl40
\margr40
{\colortbl\red0\green0\blue0;}
\pard\tx520\tx1060\tx1600\tx2120\tx2660\tx3200\tx3720\tx4260\tx4800\tx5320\f0\b0\i0\ul0\fs24\fc0 This application addresses the Traveling Salesman Problem, which requires that a salesman visiting N different cities find the shortest possible route that passes through each city once and only once. It uses Simulated Annealing, an algorithm for efficiently solving nonlinear optimization problems. This problem is NP-complete: The computation time increases exponentially as the number of cities increases. For the Traveling Salesman Problem, there are (N-1)! /2 distinct routes to search. For example, with 14 cities, there are 3.1 billion routes. In this demonstration, Simulated Annealing can find a good solution usually within a few thousand trials. Although not guaranteed to get the best solution, Simulated Annealing will find a good one, which is often all one really needed, while saving a great deal of time. The above example is on the order of a million times faster than checking all possible routes.\
The locations of the cities can be entered into the scroll view (Cities) or can be added to it by mouse clicking the map (maximum of 30 cities). When clicking on the map the cursor point whose coordinates appear just below the map can be dragged to whatever location on the map before being released and added to the list. An already existing city can be moved by clicking within its circle and dragging it. When entering cities directly through the scroll view one must first display them using "Plot Cities" before one can find the route.\
Initial Temperature and Test for Freezing are parameters used to control how the algorithm runs and the quality of the final path. Generally speaking, the higher these values the more optimal the final route and the longer needed to run. As initial estimates, Initial Temperature is set at 5 times the initial path length, and Test is set at 10 times the number of cities.\
In this application the default cooling schedule reduces the temperature inverse-proportionally to the number of iterations. In addition, one can turn on a ``Latent Heat'' cooling schedule that allows the temperature to decrease based on changes in the path length [ Davis et al., ``An adaptive cooling schedule for simulated annealing with application to multiple-constraint time-domain beamforming'', J. Acoust. Soc. Am., Suppl. 1, Vol. 88 (1990)]. This cooling schedule has been found to have a nearly exponential cooling rate in spurts, and can significantly decrease the number of iterations required to reach a good solution.\
Trials Between Plotting determines how often the intermediate trial routes will be plotted. Any negative number causes it to plot only the final route. Note the more you plot the slower it will run. Runs usually have several hundred to several thousand trials.
(.txt)